package labox.innovation.gameserver.pathfinding.utils;

import java.util.LinkedList;

import labox.innovation.config.Config;
import labox.innovation.gameserver.pathfinding.Node;

/**
 * ����Ѵ����࣬�㷨ʱ�临�Ӷ�O�S2
 * 
 * @author squll
 */
public final class BinaryNodeHeap {

	private static final LinkedList<BinaryNodeHeap> _buff = new LinkedList<BinaryNodeHeap>();

	private final Node[] _list;

	private int _size;

	public static final BinaryNodeHeap newInstance() {
		BinaryNodeHeap heap = _buff.poll();
		if (heap == null)
			return new BinaryNodeHeap(Config.PATHFINDING_MAX_NODE);
		heap._size = 0;
		return heap;
	}

	public static final void recycle(BinaryNodeHeap recycle) {
		if (recycle != null)
			_buff.add(recycle);
	}

	private BinaryNodeHeap(int size) {
		_list = new Node[size + 1];
		_size = 0;
	}

	public boolean add(Node n) {
		Node[] openList = _list;
		if (_size >= openList.length)
			return false;
		openList[_size++] = n;
		int bottom = _size - 1;
		int half = bottom + 1;
		Node a, b;
		for (;;) {
			half >>= 1;
			if (half == 0)
				break;
			a = openList[half - 1];
			b = openList[bottom];
			if (a.getCost() > b.getCost()) {
				openList[half - 1] = b;
				openList[bottom] = a;
				bottom = half - 1;
			} else
				break;
		}
		return true;
	}

	public Node removeFirst() {
		int size, half;
		Node[] openList = _list;
		Node result = openList[0];
		Node bottom = openList[_size - 1];
		openList[--_size] = null;
		int index = _size - 1;
		if (index < 0)
			return result;
		size = 0;
		openList[size] = bottom;
		half = size + 1;

		Node a, b, c;
		for (;;) {
			half <<= 1;
			if (half - 1 > index)
				break;
			a = openList[half - 1];
			if (half <= index) {
				b = openList[half];
				if (a.getCost() > b.getCost()) {
					c = openList[size];
					if (c.getCost() > b.getCost()) {
						openList[half] = c;
						openList[size] = b;
						size = half;
						half += 1;
					} else
						break;
				} else {
					c = openList[size];
					if (c.getCost() > a.getCost()) {
						openList[half - 1] = c;
						openList[size] = a;
						size = half - 1;
					} else
						break;
				}
			} else {
				c = openList[size];
				if (c.getCost() > a.getCost()) {
					openList[half - 1] = c;
					openList[size] = a;
					size = half - 1;
				} else
					break;
			}

		}
		return result;
	}

	public boolean contains(Node n) {
		for (int i = _size; --i >= 0;) {
			if (_list[i] == n)
				return true;
		}
		return false;
	}

	public boolean isEmpty() {
		return _size == 0;
	}
}
